package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code51NumberOfIsland {

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    inflect(grid, i, j);
                }
            }
        }
        return count;
    }

    public void inflect(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
            return;
        }
        // 修改为其他值, 防止重复访问
        grid[i][j] = '2';
        inflect(grid, i - 1, j);
        inflect(grid, i + 1, j);
        inflect(grid, i, j - 1);
        inflect(grid, i, j + 1);
    }


    public int numIslands1(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return 0;
        }
//        UnionFound unionFound = new UnionFound(grid);
//        for (int i = 0; i < grid.length; i++) {
//            for (int j = 0; j < grid[0].length; j++) {
//                if (grid[i][j] == '1') {
//                    if (i >= 1 && grid[i - 1][j] == '1') {
//                        unionFound.union(i, j, i - 1, j);
//                    }
//                    if (i < grid.length - 1 && grid[i + 1][j] == '1') {
//                        unionFound.union(i, j, i + 1, j);
//                    }
//                    if (j >= 1 && grid[i][j - 1] == '1') {
//                        unionFound.union(i, j, i, j - 1);
//                    }
//                    if (j < grid[0].length - 1 && grid[i][j + 1] == '1') {
//                        unionFound.union(i, j, i, j + 1);
//                    }
//                }
//            }
//        }
        int m = grid.length;
        int n = grid[0].length;
        UnionFound unionFound = new UnionFound(grid);
        for (int j = 1; j < n; j++) {
            if (grid[0][j - 1] == '1' && grid[0][j] == '1') {
                unionFound.union(0, j - 1, 0, j);
            }
        }
        for (int i = 1; i < m; i++) {
            if (grid[i - 1][0] == '1' && grid[i][0] == '1') {
                unionFound.union(i - 1, 0, i, 0);
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (grid[i][j] == '1') {
                    // 左
                    if (grid[i][j - 1] == '1') {
                        unionFound.union(i, j, i, j - 1);
                    }
                    // 上
                    if (grid[i - 1][j] == '1') {
                        unionFound.union(i, j, i - 1, j);
                    }
                }
            }
        }
        return unionFound.count();
    }

    static class UnionFound {
        private final int[] parent;
        private final int[] rank;
        private int count;
        private final int n;

        public UnionFound(char[][] grid) {
            int m = grid.length;
            this.n = grid[0].length;
            this.parent = new int[m * n];
            this.rank = new int[m * n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        int index = index(i, j);
                        parent[index] = index;
                        rank[index] = 1;
                        count++;
                    }
                }
            }
        }

        public int index(int r, int c) {
            return r * n + c;
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x1, int y1, int x2, int y2) {
            int fx = find(index(x1, y1));
            int fy = find(index(x2, y2));
            if (fx != fy) {
                if (rank[fx] < rank[fy]) {
                    parent[fx] = fy;
                    rank[fy] += rank[fx];
                } else {
                    parent[fy] = fx;
                    rank[fx] += rank[fy];
                }
                count--;
            }
        }

        public int count() {
            return count;
        }
    }
}
